原题地址:两数之和 II - 输入有序数组
给定一个已按照 升序排列 的有序数组,找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2,其中 index1 必须小于 index2。
说明:
- 返回的下标值(index1 和 index2)不是从零开始的。
- 你可以假设每个输入只对应唯一的答案,而且你不可以重复使用相同的元素。
示例:
输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
双指针法
由于数组已经有序,所以可以设置双指针,分别从左右端点出发,根据两数之和与目标数的大小决定移动哪一个指针,这样只需要一次遍历就可以找到目标数。
具体的实现方法如下:
/**
* @param {number[]} numbers
* @param {number} target
* @return {number[]}
*/
// 双指针法
const twoSum1 = function(numbers, target) {
// 左右双指针
let [left, right] = [0, numbers.length - 1];
while (left < right) {
let sum = numbers[left] + numbers[right];
// 找到了目标数
if (sum === target) {
return [left + 1, right + 1];
}
// 没有找到则根据和与目标数的大小决定移动哪个指针
if (sum < target) {
left ++;
} else {
right --;
}
}
};
测试:
let start = new Date();
const test = twoSum1;
console.log(test([2, 7, 11, 15],9)); // [1,2]
console.log(new Date().getTime() - start.getTime()); // 3
时间复杂度: 一次遍历,时间复杂度为$O(N)$
空间复杂度: 常数级额外空间,空间复杂度为$O(1)$
本文由 李海平 创作,采用 知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
最后编辑时间为: Oct 14,2019